3. 逻辑公式

日常语言有时是模棱两可的，这就给严密的数学证明带来了麻烦。因此我们有必要引入一系列用于描述关系的符号系统，这就是 命题。为了形式化描述命题之间的关系，我们引入用于指代命题本身的符号——命题变量。命题变量又称 布尔变量，指代了一个确定但未知的命题，其值只有 TRUE 与 FALSE 两种。我们可以使用 逻辑运算符 将基本的命题变量组合起来形成更大的 命题公式。

常见的逻辑运算符包括：

其具体含义不再赘述。

真值表 可以精确描述当命题公式中的每个变量取某一确定值时，整个命题公式的值。两个公式 等价 当且仅当两个公式的真值表相同。

对于蕴涵命题而言，称命题 P→Q 的 逆命题 为 Q→P；逆否命题为 ¬Q→¬P。蕴涵命题总与其逆否命题等价，但对逆命题不满足此性质。当且仅当命题等于两个互逆的蕴涵命题的逻辑与。

无论变量如何取值，总是为真的命题公式为 重言式（又称 永真式、有效公式）；对应总为假的命题公式为 矛盾式。等价即为用真的一个特例，即若 P 与 Q 等价，则 P↔Q 为重言式。可满足式 则指代在某些给定的命题变量取值下 能够为真 的命题公式。一个式子为可满足式当且仅当其否命题是不是重言式，这被称作 可满足性（SAT） 问题。然而，说起来简单做起来难，SAT 问题属于NP 问题。

除了通过真值表判断两个命题公式是否等价外，还可以通过使用代数证明，将命题公式通过一系列等价关系化简为同一命题公式来判断。由于每一个命题公式都有一个等价的 析取范式 或 合取范式，在判断命题等价性时，我们可以将命题转换为某个变量集合上的析取范式或合取范式来判断。

前面 提到过 谓词 指的是命题真假性取决于其自变量取值的命题。我们使用 量词 描述谓词为真的频率，得到 谓词公式。量词分为 全称量词 ∀ 与 存在量词 ∃。其具体含义不再赘述。

当我们在谓词公式中使用多个量词时，量词间的顺序会影响谓词的含义，进而影响其在何时为真。

此外，谓词中变量的取值也会影响命题本身的真假性，如果公式中的所有变量都来自同一个非空集合，我们可以省略，这个集合被称作该谓词公式的 域。

如果一个谓词公式在变量所有可能的非空域上，对于任何谓词都成立，则这是一个 永真式，其可以用于给谓词公式做等价转换，常见的转换关系有：

如果谓词公式在域的某个部分上或当谓词取某些具体含义时不成立，这些被叫做该公式的 反模式。

为了证明某个谓词公式是有效公式，可以使用如下四个基本的推理规则：

古德尔完备性定理指出，所有命题公式的有效性都可判定；但古德尔第一不完备性定理指出，在拥有足够强算术公理的体系内一定存在一些无法证明的真命题。